package com.duoduo.深度广度优先;

import com.duoduo.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @program: algorithm
 * @description: 102
 * 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
 * 输入：root = [3,9,20,null,null,15,7]
 * 输出：[[3],[9,20],[15,7]]
 * @author: chaidl  ！
 * @create: 2022-02-28 21:15
 */
public class 二叉树的层序遍历 {
    public static void main(String[] args) {
        TreeNode A = new TreeNode(3);
        TreeNode c = new TreeNode(9);
        TreeNode v = new TreeNode(20);
        TreeNode l = new TreeNode(15);
        TreeNode j = new TreeNode(7);
        A.left = c;
        A.right = v;
        v.left=l;
        v.right=j;
        System.out.println(levelOrder(A));
    }
    //广度优先遍历的写法模式
    //1.使用队列
    //2.在队列非空的时候，动态取出队首元素
    //3.取出队首元素的时候，把队首元素相邻的结点（非空）加入队列
    /**
     * 广度优先
     *
     * @param root
     * @return
     */
    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result=new ArrayList<>();
        if (root==null){
            return result;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        // 先把头结点放进去 队列 ，先进先出
        queue.add(root);
        while (!queue.isEmpty()){
            // 注意 1：一定要先把当前队列的结点总数暂存起来
            int currentSize = queue.size();
            List<Integer> list=new ArrayList<>();
            for (int i = 0; i < currentSize; i++) {
            //    从队列中依次取出数据放入数组
                TreeNode poll = queue.poll();
                list.add(poll.val);
                // 注意 2：左（右）孩子结点非空才加入队列
                if (poll.left!=null){
                    queue.offer(poll.left);
                }
                if (poll.right!=null){
                    queue.offer(poll.right);
                }
            }
            result.add(list);
        }
        return result;
    }
}
